﻿/*
大菲波数 
Time Limit:1000MS  Memory Limit:32768K

  
Description:
Fibonacci数列，定义如下： f(1)=f(2)=1 f(n)=f(n-1)+f(n-2) n>=3。计算第n项Fibonacci数值。 

Input:
输入第一行为一个整数N，接下来N行为整数Pi（1<=Pi<=1000）。 
Output:
输出为N行，每行为对应的f(Pi)。 
Sample Input:
5
1
2
3
4
5
Sample Output:
1
1
2
3
5
*/
#include <iostream>
#include <vector>
#include <algorithm>
//#include <cmath>
using namespace std;

#define MAX(a,b) (((a)>(b))?(a):(b))

enum
{
	base = 10000
};
int main()
{
	int n; 
	cin >> n;

	vector<int> v;
	v.reserve(n);
	for (int num;n-- && cin >> num; v.push_back(num))
		;

	int maximum = *max_element(v.begin(), v.end());

	vector<vector<int> > fibs;
	fibs.reserve(maximum-1);
	//vector<int> fib1(1,1);
	fibs.push_back(vector<int>(1, 1));
	//vector<int> fib2(1,1);
	fibs.push_back(vector<int>(1, 1));

	cout<<endl;
	for (int i = 2; i <= maximum; ++i)
	{
		vector<int> &fib1 = fibs[i - 1], &fib2 = fibs[i - 2];
		vector<int>::size_type size1 = fib1. size(), size2 = fib2.size();
		vector<int> fib;
		fib.assign(MAX(size1, size2), 0);

// 		copy(fib1.rbegin(), fib1.rend(), ostream_iterator<int>(cout, " "));
// 		cout<<",";
// 		copy(fib2.rbegin(), fib2.rend(), ostream_iterator<int>(cout, " "));
// 		cout<<endl;

		for (int k = 0; k < size1 && k < size2; ++k)
		{
			int sum = fib1[k] + fib2[k];
			fib[k] += sum % base;
			int carry = sum / base;
			if (carry)
				fib[k + 1] += carry;
		}
		for (; k < size1; ++k)
		{
			fib[k] += fib1[k];
			fib[k] %= base;
			fib[k + 1] += fib[k] / base;
		}
		for (; k < size2; ++k)
		{
			fib[k] += fib2[k];
			fib[k] %= base;
			fib[k + 1] += fib[k] / base;
		}
		fibs.push_back(fib);
	}

	for (vector<int>::iterator vit=v.begin(); vit!=v.end(); ++vit)
	{
		
		//	for (vector< vector<int> >::iterator fit=fibs.begin(); fit!=fibs.end(); ++fit)
		//	{
		//vector<int>& fib=*fit;
		vector<int>& fib=fibs[*vit-1];
		for (vector<int>::reverse_iterator rit=fib.rbegin(); rit!=fib.rend(); ++rit)
			cout<<*rit;
		cout<<endl;
	//	}

	}



	return 0;
}